By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 18, Issue 2, pp. 209-427

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

A Lower Bound on the Complexity of Division in Finite Extension Fields and Inversion in Quadratic Alternative Algebras

Thomas Lickteig

pp. 209-215

BibTeX  Abstract Full Text:  PDF

Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared-Memory Machines

Gianfranco Bilardi and Alexandru Nicolau

pp. 216-228

BibTeX  Abstract Full Text:  PDF

The Token Distribution Problem

David Peleg and Eli Upfal

pp. 229-243

BibTeX  Abstract Full Text:  PDF

Scheduling Precedence Graphs in Systems with Interprocessor Communication Times

Jing-Jang Hwang, Yuan-Chieh Chow, Frank D. Anger, and Chung-Yee Lee

pp. 244-257

BibTeX  Abstract Full Text:  PDF

Finding an Approximate Maximum

N. Alon and Y. Azar

pp. 258-267

BibTeX  Abstract Full Text:  PDF

Bounds on Universal Sequences

Amotz Bar-Noy, Allan Borodin, Mauricio Karchmer, Nathan Linial, and Michael Werman

pp. 268-277

BibTeX  Abstract Full Text:  PDF

Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization

J. Michael Steele and Timothy Law Snyder

pp. 278-287

BibTeX  Abstract Full Text:  PDF

Optimal Parallel $5$-Colouring of Planar Graphs

Torben Hagerup, Marek Chrobak, and Krzysztof Diks

pp. 288-300

BibTeX  Abstract Full Text:  PDF

Nonblocking Multirate Networks

Riccardo Melen and Jonathan S. Turner

pp. 301-313

BibTeX  Abstract Full Text:  PDF

Minimizing Schedule Length Subject to Minimum Flow Time

Joseph Y-T. Leung and Gilbert H. Young

pp. 314-326

BibTeX  Abstract Full Text:  PDF

Fast Parallel Algorithms for Chordal Graphs

Joseph Naor, Moni Naor, and Alejandro A. Schäffer

pp. 327-349

BibTeX  Abstract Full Text:  PDF

On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials

James Renegar

pp. 350-370

BibTeX  Abstract Full Text:  PDF

Partitioning Space for Range Queries

F. Frances Yao, David P. Dobkin, Herbert Edelsbrunner, and Michael S. Paterson

pp. 371-384

BibTeX  Abstract Full Text:  PDF

CNF-Satisfiability Test by Counting and Polynomial Average Time

Kazuo Iwama

pp. 385-391

BibTeX  Abstract Full Text:  PDF

Relativized Polynomial Time Hierarchies Having Exactly $K$ Levels

Ker-I Ko

pp. 392-408

BibTeX  Abstract Full Text:  PDF

Exponential Average Time for the Pure Literal Rule

Khaled M. Bugrara, Youfang Pan, and Paul Walton Purdom, Jr.

pp. 409-418

BibTeX  Abstract Full Text:  PDF

A New Parallel Algorithm for the Maximal Independent Set Problem

Mark Goldberg and Thomas Spencer

pp. 419-427

BibTeX  Abstract Full Text:  PDF